package ar.com.e2solver.solver.operator.crossover.impl;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;

import ar.com.e2solver.exception.BusinessException;
import ar.com.e2solver.model.Coordinate;
import ar.com.e2solver.model.Piece;
import ar.com.e2solver.model.Puzzle;
import ar.com.e2solver.solver.Individual;
import ar.com.e2solver.solver.RandomConstants;
import ar.com.e2solver.solver.operator.OperatorUtil;
import ar.com.e2solver.solver.operator.crossover.CrossoverOperator;

/**
 * Dados dos individuos crea un tercero que es el resultado de pasar del
 * rompecabezas con mas fitness un camino de buenas piezas. El camino de buenas
 * piezas se busca seleccionando dos piezas random y buscando el camino minimo
 * entre ellas.
 * 
 * Por camino minimo se entiende a aquel que contiene mas piezas con bordes
 * iguales. El peso del borde (eje) entre dos piezas es 1 si el borde es
 * distinto o 0 si el borde coincide.
 * 
 * @author rodo
 * 
 */
public final class ShortestPathCrossOverOperator implements CrossoverOperator {

	private static ShortestPathCrossOverOperator instance = new ShortestPathCrossOverOperator();
	
	private ShortestPathCrossOverOperator(){}
	
	public static ShortestPathCrossOverOperator getInstance(){
		return instance;
	}
	
	public List<Individual> operate(Individual individual1, Individual individual2) throws BusinessException {
		int rows = individual1.getPuzzle().getRowsNumber();
		int cols = individual1.getPuzzle().getColumnNumbers();

		Puzzle bestPuzzle, worstPuzzle;
		bestPuzzle = individual1.getPuzzle();
		worstPuzzle = individual2.getPuzzle();

		// selecciona dos coordenadas random
		Coordinate c1 = RandomConstants.getRandomCoordinate(rows, cols);
		Coordinate c2 = RandomConstants.getRandomCoordinate(rows, cols);

		// busca el camino minimo entre las coordenadas sobre el mejor rompecabezas
		Map<Coordinate, Piece> pathPieces = getShortestPath(bestPuzzle, c1, c2);
		
		// pone en el nuevo rompecabezas el camino encontrado
		Puzzle newPuzzle = worstPuzzle.clone();
		merge(newPuzzle, pathPieces);
		
		List<Individual> result = new ArrayList<Individual>(1);
		result.add(new Individual(newPuzzle));
		return result;
	}

	public Map<Coordinate, Piece> getShortestPath(Puzzle puzzle, Coordinate initial, Coordinate target) {
		Map<Coordinate, Coordinate> previousPath = new HashMap<Coordinate, Coordinate>();
		Set<Coordinate> visited = new HashSet<Coordinate>();
		Map<Coordinate, Integer> distances = new HashMap<Coordinate, Integer>();
		
		distances.put(initial, 0);
		Coordinate current = initial;
		
		while(!current.equals(target)){
			Map<Coordinate, Integer> unvisitedNeighborsDistance = getUnvisitedNeighborsDistance(puzzle, current, visited);
			
			for (Entry<Coordinate,Integer> entry : unvisitedNeighborsDistance.entrySet()) {
				Integer newDistance = distances.get(current) + entry.getValue();
				
				if(!distances.containsKey(entry.getKey()) || distances.get(entry.getKey()) > newDistance){
					distances.put(entry.getKey(), newDistance);
					previousPath.put(entry.getKey(), current);
				}
			}
			
			visited.add(current);
			current = getNextCoordinate(distances, visited);
		}
		
		return assemblePath(previousPath, target, puzzle);
	}

	private Map<Coordinate, Integer> getUnvisitedNeighborsDistance(Puzzle puzzle, Coordinate current, Set<Coordinate> visited) {
		Map<Coordinate, Integer> unvisitedNeighborsDistance = new HashMap<Coordinate, Integer>();
		if(current.getX() != 0){
			Coordinate top = new Coordinate(current.getX() - 1, current.getY());
			if(!visited.contains(top)){
				int topDistance = (puzzle.getPieceAt(top).getBottom().equals(puzzle.getPieceAt(current).getTop()))? 1 : 10;
				unvisitedNeighborsDistance.put(top, topDistance);
			}
		}
		
		if(current.getY() != 0){
			Coordinate left = new Coordinate(current.getX(), current.getY() - 1);
			if(!visited.contains(left)){
				int leftDistance = (puzzle.getPieceAt(left).getRight().equals(puzzle.getPieceAt(current).getLeft()))? 1 : 10;
				unvisitedNeighborsDistance.put(left, leftDistance);
			}
		}
		
		if(current.getX() < puzzle.getRowsNumber() -1){
			Coordinate bottom = new Coordinate(current.getX() + 1, current.getY());
			if(!visited.contains(bottom)){
				int bottomDistance = (puzzle.getPieceAt(bottom).getTop().equals(puzzle.getPieceAt(current).getBottom()))? 1 : 10;
				unvisitedNeighborsDistance.put(bottom, bottomDistance);
			}
		}
		
		if(current.getY() < puzzle.getColumnNumbers() -1){
			Coordinate right = new Coordinate(current.getX(), current.getY() + 1);
			if(!visited.contains(right)){
				int rightDistance = (puzzle.getPieceAt(right).getLeft().equals(puzzle.getPieceAt(current).getRight()))? 1 : 10;
				unvisitedNeighborsDistance.put(right, rightDistance);
			}
		}
		
		return unvisitedNeighborsDistance;
	}
	
	private Coordinate getNextCoordinate(Map<Coordinate, Integer> distances, Set<Coordinate> visited) {
		Coordinate result = null;
		int minDistance = 0;
		
		for (Entry<Coordinate, Integer> entry : distances.entrySet()) {
			if(!visited.contains(entry.getKey())){
				
				if(result == null || minDistance > entry.getValue()){
					result = entry.getKey();
					minDistance = entry.getValue();
				}
			}
		}
		return result;
	}

	private Map<Coordinate, Piece> assemblePath(	Map<Coordinate, Coordinate> previousPath, Coordinate target, Puzzle puzzle) {
		Map<Coordinate, Piece> result = new HashMap<Coordinate, Piece>();
		
		Coordinate t = target;
		while(previousPath.containsKey(t)){
			result.put(t, puzzle.getPieceAt(t));
			t = previousPath.get(t);
		}
		
		result.put(t, puzzle.getPieceAt(t));
		return result;
	}
	
	private void merge(Puzzle puzzle, Map<Coordinate, Piece> pathPieces) throws BusinessException {
		
		Coordinate coordinate= null;
		for (Entry<Coordinate, Piece> entry : pathPieces.entrySet()) {
			coordinate = entry.getKey();
			Coordinate c = puzzle.findCoordinateForPiece(entry.getValue());
			if(puzzle.canSwap(coordinate, c)){
				puzzle.swapPositions(coordinate, c);
				
				Piece p1 = puzzle.getPieceAt(coordinate);
				Piece pathPiece = pathPieces.get(coordinate);
				while(!p1.equalPositionAndColor(pathPiece)){
					p1.rotateToRight(1);
				}
				
				if(puzzle.getPieceAt(c).isABorderPiece()){
					OperatorUtil.rotateForBorder(c, puzzle);
				}
				
				if(puzzle.getPieceAt(c).isACornerPiece()){
					OperatorUtil.rotateForCorner(c, puzzle);
				}
			}
			
		}
	}
}
